416. 分割等和子集

Similar Question

这道题目初步看，和如下两题几乎是一样的，大家可以用回溯法，解决如下两题

• 698.划分为 k 个相等的子集
• 473.火柴拼正方形

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

本题是可以用回溯暴力搜索出所有答案的，但最后超时了，也不想再优化了，放弃回溯，直接上 01 背包吧。

Solution Tips

方案一: 01 背包问题

代码随想录

主要要理解，题目中物品是 nums[i]，重量是 nums[i]，价值也是 nums[i]，背包体积是 sum/2。

如果 dp[j] == j 说明，集合中的子集总和正好可以凑成总和 j，理解这一点很重要

var canPartition = function(nums) {
    const sum = (nums.reduce((p, v) => p + v));
    if (sum & 1) return false;
    const dp = Array(sum / 2 + 1).fill(0);
    for(let i = 0; i < nums.length; i++) {
        for(let j = sum / 2; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            if (dp[j] === sum / 2) {
                return true;
            }
        }
    }
	// 这里的作用就是返回 false 而已
    return false;
};